package sort.swap;

import java.util.Arrays;

public class QuickSort {

    public static int getMid(int[] array,int left,int right) {
        //寻找参考index
        int index = array[left];
        while (left < right) {
            while (array[right] >= index && left < right) {
                right--;
            }
            array[left] = array[right];

            while (array[left] <= index && left < right) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = index;
        index = left;
        return index;
    }

    public static void quickSort(int[] array,int left,int right) {
        int index = 0;

        if (left < right) {
            index = getMid(array, left, right);
            quickSort(array, left, index - 1);
            quickSort(array, index + 1, right);
        }
    }

    //选择array[left]，array[right]，array[left+right/2]的中间值
    public int getMiddle(int[] array,int left,int right) {
        int index = 0;
        if ((array[left] - array[right])*((array[left+right/2]) - array[left]) > 0) {
            index = array[left];
        } else if ((array[right] - array[left])*(array[left+right/2] - array[right]) > 0) {
            index = array[right];
            array[right] = array[left];
            array[left] = index;
        } else {
            index = array[left+right/2];
            array[left+right/2] = array[left];
            array[left] = index;
        }
        return index;
    }

    public int setMiddleSort(int[] array,int left,int right) {
        int index = array[left];

        while (left < right) {
            while (left < right && array[right] >= index) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= index) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = index;
        index = left;
        return index;
    }

    public void quickSortZ(int[] array,int left,int right) {
        if (array != null && array.length > 0) {
            int index = 0;

            if (left < right) {
                index = setMiddleSort(array, left, right);
                quickSortZ(array,left,index - 1);
                quickSortZ(array,index + 1,right);
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {2,4,3,9,8,7,6,5};
        QuickSort quickSort = new QuickSort();
        System.out.println(quickSort.getMiddle(array, 0, array.length - 1));
        quickSort.quickSortZ(array,0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}
